#include "main/utils.h"
using namespace std;

int mysqrt(const int &num) {
  int begin = 1;
  int end = num;
  while (begin <= end) {
    int mid = begin + ((end - begin) >> 1);
    if (mid <= num / mid) {
      if ((mid + 1)  > num / (mid + 1)) {
        return mid;
      }
      begin = mid + 1;
    } else {
      end = mid - 1;
    }
  }
  return -1;
}

int main() {
  cout << mysqrt(1) << endl;
  cout << mysqrt(4) << endl;
  cout << mysqrt(5) << endl;
  cout << mysqrt(8) << endl;
  cout << mysqrt(9) << endl;
  cout << mysqrt(16) << endl;

  return 0;
}
